package 基础篇;

public class 单边循环快排 {
    public static void main(String[] args) {
        int[] array = {4,1,7,2,9,6,12,10};
        paixu(array, 0, array.length-1);
        for (int i : array) {
            System.out.println(i);
        }
    }

    static void paixu(int[] array, int leftIndex, int rightIndex){
        if(leftIndex >= rightIndex){
            return ;
        }
        // 第一轮循环
        int calculate = calculate(array, leftIndex, rightIndex);
        paixu(array, leftIndex, calculate-1);
        paixu(array, calculate +1 , rightIndex);
    }

    static int calculate(int[] array, int leftIndex, int rightIndex){
        // 边界值
        int maxIndexValue = array[rightIndex];
        // i 先等于左边界索引
        int i = leftIndex;
        for(int j = leftIndex; j < rightIndex; j++){
            // 索引j的值小于有边界值，则将i和j的值替换
            if(array[j] < maxIndexValue){
                if(i != j){
                    swap(array, i, j);
                    i++;

                }
            }
        }
        // 将i和有边界的值替换
        swap(array, i, rightIndex);
        return i;
    }

    static void swap(int[] array, int startIndex, int endIndex){
        int a = array[startIndex];
        array[startIndex] = array[endIndex];
        array[endIndex] = a;
    }
}
